#include <stdio.h>
#include <stdlib.h>

void merge(int InputArray[],int WorkArray[],int begin,int length,int middle2)
{
	int j = 0;
	int k = middle2;
	for (int i = begin; i<length+begin;i++)
	{
		if (j==middle2)
		{
			InputArray[i] = WorkArray[k++];
		}
		else
		{
			if (k == length)
			{
				InputArray[i] = WorkArray[j++];
			}
			else
			{
				if (WorkArray[j] > WorkArray[k])
				{
					InputArray[i] = WorkArray[k++];
				}
				else 
				{
					InputArray[i] = WorkArray[j++];
				}
			}
		}
	}
}
void merge_sort(int InputArray[],int begin,int end)
{
	if(begin == end)
	{
		return;
	}
	int middle = 0;
	int middle2 = 0;
	int f = 0;
	int length = 0;

	middle  = begin + end;
	merge_sort(InputArray, begin, middle / 2);
	merge_sort(InputArray, middle / 2 + 1, end);	
	length  = end - begin + 1;
	int *WorkArray = new int[length];

	for (int i = 0; i < length; i++)
	{
		WorkArray[i] = InputArray[begin + i];
	}
	middle2 = middle / 2 - begin + 1;

	merge(InputArray,WorkArray,begin,length,middle2);
	free (WorkArray);
}

int main() 
{
	int n = 0;
	
	printf("Enter the number of elements to be sorted:");
	scanf("%d",&n);
	printf("Enter the elements to be sorted:\n");
	int *InputArray = new int [n];
	for(int i = 0; i < n; i++ )
	{
		scanf("%d",&InputArray[i]);
	}

	printf("Before sorting:");
	for(int i = 0; i < n; i++)
	printf(" %d", InputArray[i]);

	printf("\n");

	merge_sort( InputArray, 0, n - 1);

	printf("After sorting:");
	for(int i = 0; i < n; i++)
	{
		printf(" %d", InputArray[i]);
	}
	free(InputArray);

	printf("\n");
	return 0;
}